class Solution
{
public:
    vector<int> maxSumOfThreeSubarrays(vector<int> &nums, int k)
    {
        int n = nums.size();
        vector<int> maxSubArrayAhead(n);
        vector<int> maxSubArrayAheadIndex(n);
        vector<int> maxSubArrayBehind(n);
        vector<int> maxSubArrayBehindIndex(n);

        int sum = 0;
        for (int i = 0; i < k; ++i)
        {
            sum += nums[i];
        }
        maxSubArrayAhead[k - 1] = sum;
        maxSubArrayAheadIndex[k - 1] = 0;
        for (int i = k; i < n; ++i)
        {
            sum += nums[i];
            sum -= nums[i - k];
            if (sum > maxSubArrayAhead[i - 1])
            {
                maxSubArrayAhead[i] = sum;
                maxSubArrayAheadIndex[i] = i - k + 1;
            }
            else
            {
                maxSubArrayAhead[i] = maxSubArrayAhead[i - 1];
                maxSubArrayAheadIndex[i] = maxSubArrayAheadIndex[i - 1];
            }
        }

        sum = 0;
        for (int i = n - 1; i >= n - k; --i)
        {
            sum += nums[i];
        }
        maxSubArrayBehind[n - k] = sum;
        maxSubArrayBehindIndex[n - k] = n - k;
        for (int i = n - k - 1; i >= 0; --i)
        {
            sum += nums[i];
            sum -= nums[i + k];
            if (sum >= maxSubArrayBehind[i + 1])
            {
                maxSubArrayBehind[i] = sum;
                maxSubArrayBehindIndex[i] = i;
            }
            else
            {
                maxSubArrayBehind[i] = maxSubArrayBehind[i + 1];
                maxSubArrayBehindIndex[i] = maxSubArrayBehindIndex[i + 1];
            }
        }

        int midSum = 0;
        for (int i = k; i < 2 * k; ++i)
        {
            midSum += nums[i];
        }
        int maxSum = maxSubArrayAhead[k - 1] + midSum + maxSubArrayBehind[2 * k];
        vector<int> result = {maxSubArrayAheadIndex[k - 1], k, maxSubArrayBehindIndex[2 * k]};
        for (int i = k + 1; i < n - k; ++i)
        {
            midSum += nums[i + k - 1];
            midSum -= nums[i - 1];
            int sum = maxSubArrayAhead[i - 1] + midSum + maxSubArrayBehind[i + k];
            if (sum > maxSum)
            {
                maxSum = sum;
                result = {maxSubArrayAheadIndex[i - 1], i, maxSubArrayBehindIndex[i + k]};
            }
        }
        return result;
    }
};